﻿using System.Data;
using System.Runtime.InteropServices;

namespace 一维数组
{
    internal class Program
    {
        // <summary>
        /// 数组的两种声明方式
        /// </summary>
        public void init()
        {
            int[] arr = { 1, 2, 3, 4, 5 }; // 第一种声明方式
            int[] arr2 = new int[5]; // 第二种声明方式
            for (int i = 0; i < arr2.Length; i++) // 初始化数组
            {
                arr2[i] = i;
            }
            showArray(arr);
            showArray(arr2);
            int[] arr3 = new int[5]; // 第三种声明方式   
            arr3[0] = 1;
            arr3[1] = 2;
            arr3[2] = 3;
            arr3[3] = 4;
            Console.WriteLine(arr3.Length);

        }

        public void xunhuan()
        {
            // 第一种初始化方式
            int[] arr = { 1, 2, 3 };
            int a = sum(arr);
            Console.WriteLine(a);
            showArray(arr);

            // 第二种初始化方式
            int[] brr = new int[5];

            for (int i = 0; i < 5; i++)
            {
                brr[i] = i;
            }

            showArray(brr);


            string str = "hello world";
            char[] carr = str.ToCharArray();
            foreach (char c in carr)
            {
                Console.WriteLine(c);
            }
        }

        public static void showArray(int[] arr)
        {
            //for (int i = 0; i < arr.Length; i++)
            //{
            //    Console.WriteLine(arr[i]);
            //}

            // foreach 循环迭代
            foreach (int a in arr)
            {
                Console.WriteLine(a);
            }
        }

        public static int sum(params int[] nums)
        {
            int sum = 0;

            int length = nums.Length;
            for (int i = 0; i < length; i++)
            {
                sum += nums[i];
            }

            return sum;
        }

        // static void Main(string[] args)
        // {
            // Program p = new Program();
            //p.init();

            //Console.WriteLine("");
            //Console.ReadKey();

            // maopao(); // 调用冒泡排序函数

            //xuanze(); // 调用选择排序函数

            // charu(); // 调用插入排序函数

            // kuaisu(); // 调用快速排序函数
        // }


        public static void maopao()
        {
            // 初始化一个数组
            int[] arr = [3, 4, 8, 2, 9, 7, 6, 0, 5, 1];

            // 对上面的数组进行冒泡排序
            // 前一个数和后一个数进行比较，大的数往后移，经过第一轮后，最大的数在最后一位
            // 经过第二轮后，第二大的数在倒数第二位
            // 经过第三轮后，第三大的数在倒数第三位，依此类推
            for (int i = 0; i < arr.Length; i++) // 控制要比较多少轮
            {
                bool swapped = false;  //  优化：若本轮无交换，说明已有序
                // 每一轮都要比较 arr.Length - 1 - i 次
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    // 如果前一个数大于后一个数，则交换位置
                    if (arr[j] > arr[j + 1])
                    {
                        // 交换位置
                        //int temp = arr[j];
                        //arr[j] = arr[j + 1];
                        //arr[j + 1] = temp;

                        swap(ref arr[j], ref arr[j + 1]); // 调用交换函数

                        swapped = true;
                    }
                }
                if (swapped == false)
                {
                    break; // 提前结束循环
                }
            }


            // 输出排序后的数组
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");
            }
        }

        /// <summary>
        /// 选择排序
        /// 1，选择排序的基本思想是：每一轮从未排序的数据中选择最小值，放到已排序数据的末尾。
        /// 2，选择排序的时间复杂度是O(n^2)，空间复杂度是O(1)。
        /// 3，选择排序的优点是：简单易懂，适合小规模数据的排序。
        /// 4，选择排序的缺点是：时间复杂度高，不适合大规模数据的排序。
        /// 5，选择排序的稳定性：不稳定排序。
        /// 6，选择排序的应用场景：适合小规模数据的排序，比如：1000条数据以下。
        /// 7，选择排序的实现步骤：
        /// 8，从第一个数开始，假设第一个数是最小值。
        /// 9，从第二个数开始，依次与最小的数比较，如果当前数比最小值还小，则更新最小值的索引。
        /// 10，如果最小值的索引不是当前索引，则交换位置，把当前最小的往前移。
        /// 11，输出排序后的数组。
        /// </summary>
        public static void xuanze()
        {
            // 初始化一个数组
            int[] arr = [3, 4, 8, 2, 9, 7, 6, 0, 5, 1];
            // 选择排序，每一轮把未排序数据中的最小值放到已排序数据的末尾。
            // 第一轮把最小值放到第一个位置，第二轮把第二小的数放到第二个位置，依此类推。
            for (int i = 0; i < arr.Length - 1; i++)
            {
                // 假设第一个数是最小值
                int minIndex = i;

                // 从第二个数开始比较
                for (int j = i + 1; j < arr.Length; j++)
                {
                    // 如果当前数比最小值还小，则更新最小值的索引
                    if (arr[j] < arr[minIndex])
                    {
                        minIndex = j;
                    }
                }

                // 如果最小值的索引不是当前索引，则交换位置，把当前最小的往前移
                if (minIndex != i)
                {
                    swap(ref arr[i], ref arr[minIndex]);
                }
            }

            // 输出排序后的数组
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");
            }
        }


        /// <summary>
        /// 插入排序
        /// 原理：
        /// 1，插入排序的基本思想是：把未排序的数据依次插入到已排序的数据中。
        /// 2，插入排序的时间复杂度是O(n^2)，空间复杂度是O(1)。
        /// 3，插入排序的优点是：简单易懂，适合小规模数据的排序。
        /// 4，插入排序的缺点是：时间复杂度高，不适合大规模数据的排序。
        /// 5，插入排序的稳定性：稳定排序。
        /// 6，插入排序的应用场景：适合小规模数据的排序，比如：1000条数据以下。
        /// 7，插入排序的实现步骤：
        /// 8，从第二个数开始，假设第一个数是最小值。
        /// 9，从第二个数开始，依次与前面的数比较，如果当前数比前面的数小，则交换位置。
        /// 10，输出排序后的数组。
        /// </summary>
        public static void charu()
        {
            // 初始化一个数组
            int[] arr = [3, 4, 8, 2, 9, 7, 6, 0, 5, 1];

            for (int i = 1; i < arr.Length; i++)
            {
                // 第一个未排序的数字
                int temp = arr[i];

                // 前面已排序数据的最后一个
                int j = i - 1;

                // 从前面以排序的最后一个开始，往前一个一个比较。
                // 如果当前数比前面一个数小，则前面的数往后挪一位，给当前数腾出位置。
                while (j >= 0 && arr[j] > temp)
                {
                    arr[j + 1] = arr[j];
                    j--; // 往前挪一位，当j==0的时候，这里最后的值是j=-1
                }
                // 当没有比当前数大的数时，把当前数插入到前面已排序的数组中。
                arr[j + 1] = temp;
            }

            // 输出排序后的数组
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");
            }

        }

        public static void kuaisu()
        {
            // 初始化一个数组
            int[] arr = [3, 4, 8, 2, 9, 7, 6, 0, 5, 1];


            int len = arr.Length;
            Console.WriteLine(len);
            int half = len / 2;
            Console.WriteLine(half);



        }


        /// <summary>
        /// 交换函数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        public static void swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
    }


    class QuickSortExample
    {
        // 主方法
        public static void Main()
        {
            int[] arr = [3, 4, 8, 2, 9, 7, 6, 0, 5, 1];
            Console.WriteLine("Original array:");
            PrintArray(arr);

            QuickSort(arr, 0, arr.Length - 1);

            Console.WriteLine("Sorted array:");
            PrintArray(arr);
        }

        // 快速排序主函数
        static void QuickSort(int[] arr, int low, int high)
        {
            if (low < high)
            {
                // pi 是分区索引，arr[pi] 现在在正确位置
                int pi = Partition(arr, low, high);

                // 递归排序分区前后的元素
                QuickSort(arr, low, pi - 1);  // en: Before pi
                QuickSort(arr, pi + 1, high); // en: After pi
            }
        }

        // 分区函数
        static int Partition(int[] arr, int low, int high)
        {
            int pivot = arr[high];  // en: Choose last element as pivot
            int i = (low - 1);      // en: Index of smaller element

            for (int j = low; j < high; j++)
            {
                // 如果当前元素小于或等于基准值
                if (arr[j] <= pivot)
                {
                    i++;
                    // 交换 arr[i] 和 arr[j]
                    Swap(ref arr[i], ref arr[j]);
                }
            }

            // 交换 arr[i+1] 和基准值 (arr[high])
            Swap(ref arr[i + 1], ref arr[high]);
            return i + 1;
        }

        // 交换函数
        static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        // 打印数组
        static void PrintArray(int[] arr)
        {
            foreach (var item in arr)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }
    }
}
